package interview.loop;

public class BinarySearch
{
	/**
	 * Searches element k in a sorted array.
	 * 
	 * @param arr
	 *            a sorted array
	 * @param k
	 *            the element to search
	 * @return index in arr where k is. -1 if not found.
	 */
	public int binarySearch(int[] arr, int k)
	{
		// 要求：1.数组有序，2.支持随机访问
		// 定义下标区间a,b
		int a = 0;
		int b = arr.length;// b指向数组元素最后一个的后一位【方便点】
		// Loop invariant: [a, b) is a valid range. (a <= b)
		// k may only be within range [a, b).

		while (a < b)
		{
			// int m = (a + b) / 2;// (a + b) / 2 may overflow!
			int m = a + (b - a) / 2;
			// a == b: m = a and m = b区间为0【已解决】
			// b == a + 1:m = a 区间为1【已解决】
			// b == a + 2:m = a+1 区间为2【已解决】区间越长越放心

			if (k < arr[m])// k取值范围：a到(m-1)
			{
				b = m;
			} else if (k > arr[m])// k取值范围：m+1到b-1
			{
				a = m + 1;
			} else
			{
				return m;// 找到了
			}
		}
		return -1;

	}

	public static void main(String[] args)
	{
		BinarySearch bs = new BinarySearch();
		System.out.println(bs.binarySearch(new int[] { 1, 2, 10, 15, 100 }, 15));
		System.out.println(bs.binarySearch(new int[] { 1, 2, 10, 15, 100 }, -2));
		System.out.println(bs.binarySearch(new int[] { 1, 2, 10, 15, 100 }, 101));
		System.out.println(bs.binarySearch(new int[] { 1, 2, 10, 15, 100 }, 13));
		System.out.println("=========");
		System.out.println(bs.binarySearch(new int[] {}, 13));
		System.out.println(bs.binarySearch(new int[] { 12 }, 13));
		System.out.println(bs.binarySearch(new int[] { 13 }, 13));
		System.out.println("=========");
		System.out.println(bs.binarySearch(new int[] { 12, 13 }, 13));
		System.out.println(bs.binarySearch(new int[] { 12, 13 }, 12));
	}

}
